package linked;

/**
 * 19. 删除链表的倒数第 N 个结点
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * <p>
 * 示例 1：
 * 输入：head = [1,2,3,4,5], n = 2
 * 输出：[1,2,3,5]
 * <p>
 * 示例 2：
 * 输入：head = [1], n = 1
 * 输出：[]
 * <p>
 * 示例 3：
 * 输入：head = [1,2], n = 1
 * 输出：[1]
 */
public class Problem_19 {

    /**
     * 快慢双指针
     * 由于我们需要找到倒数第 n 个节点，因此我们可以使用两个指针 fast 和 slow 同时对链表进行遍历，
     * 并且 fast 比 slow 超前 n 个节点。
     * 这样，当 fast 遍历到链表的末尾时，slow 就恰好处于倒数第 n 个节点。
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(); // 虚拟头节点
        dummy.next = head;

        ListNode fast = head; // 快指针
        ListNode slow = dummy; // 慢指针

        // 快指针fast 先走n步
        for (int i = 0; i < n && fast != null; i++) {
            fast = fast.next;
        }
        // 快慢指针同时后移
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 此时 慢指针slow 的下一个节点，就是倒数第n个待删除节点
        slow.next = slow.next.next;

        return dummy.next;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}
